# 记忆化搜索超时
# import functools
# class Solution(object):
#     def numberOfSets(self, n, k):
#         base = 10 ** 9 + 7
#         @functools.cache
#         def find(index, t):
#             if t == 1:
#                 return n - index - 1
#             else:
#                 val = 0
#                 for next_index in range(index + 1, n - (t - 1)):
#                     val += ((next_index - index) * find(next_index, t - 1)) % base
#                 return val % base
#
#         val = 0
#         for i in range(n - k):
#             val += find(i, k) % base
#         return val % base

import functools
# class Solution(object):
#     def numberOfSets(self, n, k):
#         base = 10 ** 9 + 7
#         @functools.cache
#         def dfs(i, j, state):
#             if j == 0:
#                 if state == 1:
#                     return 0
#                 else:
#                     return 1
#             if i == j + 1:
#                 if state == 1:
#                     return 1
#                 else:
#                     return 0
#             if state == 0:
#                 return (dfs(i - 1, j, 0) + dfs(i - 1, j, 1)) % base
#             else:
#                 return (dfs(i - 1, j - 1, 0) + dfs(i - 1, j, 1) + dfs(i - 1, j - 1, 1)) % base
#         return (dfs(n, k, 1) + dfs(n, k, 0)) % base
import math
class Solution(object):
    def numberOfSets(self, n, k):
        return math.comb(n + k - 1, 2 * k) % (10 ** 9 + 7)
